package com.xinpan.exercise;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class MergeInterval {
	   public ArrayList<Interval> merge(ArrayList<Interval> intervals) 
	   {
	        // Start typing your Java solution below
	        // DO NOT write main() function
	        if(intervals.size() <= 1)
	            return intervals;
	            
	        Collections.sort(intervals, new Comparator<Interval>(){

				@Override
				public int compare(Interval arg0, Interval arg1) {
					// TODO Auto-generated method stub
					return arg0.start > arg1.start ? 1 : (arg0.start < arg1.start ? -1 : 0);
				}
	        });
	        
	        int i = 0;
	        while(i < intervals.size()-1)
	        {
	            if(intervals.get(i).end >= intervals.get(i+1).start)
	            {
	            	int end = intervals.get(i).end > intervals.get(i+1).end ?
	            				intervals.get(i).end : intervals.get(i+1).end;
	                intervals.get(i).end = end;
	                intervals.remove(i+1);
	            }
	            else
	                i++;
	        }
	        return intervals;
	    }
	   
	  	class Interval {
		        int start;
		        int end;
		        Interval() { start = 0; end = 0; }
		        Interval(int s, int e) { start = s; end = e; }
		    }
}
